package main

// ! The power method
func power(exponent int, index int) int {
	var power int

	power = 1
	for index > 0 {
		if index&1 != 0 {
			power *= exponent
		}
		index >>= 1
		exponent *= exponent
	}
	return power
}

func ShellSorter(elements []int) {
	var (
		n         = len(elements)
		intervals = []int{1}
		k         = 1
	)
	for {
		var interval int
		interval = power(2, k) + 1
		if interval > n-1 {
			break
		}
		intervals = append([]int{interval}, intervals...)
		k++
	}

	var interval int
	// 设置间隔
	for _, interval = range intervals {
		var i int
		for i = interval; i < n; i += interval {
			var j int
			j = 1
			for j > 0 {
				// 插入排序
				if elements[j-interval] > elements[j] {
					elements[j-interval], elements[j] = elements[j], elements[j-interval]
				}
			}
		}
	}

}

func main() {

}
